Your final homework/project
is to write a program that reads in a graph and answers the question: which
nodes are reachable from a source node.
This assignment is a more manageable
subset of the general problem solved by Dijkstra which is finding the least
cost path from a source to a target node.
To start, you need to
understand what a graph is. A graph is a
group of connected nodes. A graph is
said to be a directed graph if the interconnections have a direction. A graph is said to be weighted if the connections
have an associated cost. Here is an
example:
Figure 1
4.0 1.0 2.0 2 1 3
1.0 9.0 1.0 1.0 2.0 1.0 0.5 0.5 4.0 2.5 9 8 7 4 5 6
This graph says you can get
from node 1 to node 3 at a cost of 2. It
also shows that there is a path from node 7 to node 9 at a cost of 1.5, however
there is no path from node 9 to node 7.
These nodes could represent
an interconnected set of computers. The
cost could represent the time required to send a packet from one computer to
another. The variation in cost could be
due to the speed of the interconnection.
Note that node 6 could be a secure computer that must never get a virus
and so only allows for external communication.
This means that starting at
node 1 you can not reach node 6, however, starting at node 6 you can reach all
nodes.
This type of graph could
also represent train stations and rail connections between stations. It could represent cities and a certain set
of bus routes between the cities.
The graph in figure 1 could
be represented in a file as the numbers:
1 3 2.0
2 3 4.0
2 1 1.0
3 1 1.0
3 5 2.0
4 7 0.5
4 8 0.5
5 4 2.5
6 2 1.0
6 7 1.0
6 9 9.0
7 8 0.5
8 9 1.0
9 9 0.0
-1 -1 -1.0
Where the first number is
the source node, the second is the target and the third is the cost. The negative numbers represent the end of the
data.
Now that you know what a
graph is, how do you get a computer to
traverse a graph? And more germane to
your homework, how do you use the STL to solve this problem?
There is no graph software
in the STL. However, there are
components that you can use to cobble together a solution requiring the minimum
amount of programming effort.
First we need an algorithm.
Dijkstra created an
algorithm that solves the more general case of finding the shortest path
between a source and target node, but you can use the core of his algorithm to
solve the problem of finding all nodes reachable from a source node.
The algorithm you need is
this:
Place the source node on a
stack.
While the stack is not empty
Pop the top node off of the stack and mark
it visited.
Find all nodes reachable from the current
node and, if they have not been visited, push
them onto the stack.
That is it in a
nutshell. After the stack is exhausted,
all of the visited nodes will be the ones reachable from the source node.
Now for some coding
details. We need to decide on some data
structures. We obviously need a
stack. We also need some way to store
the original nodes and the visited nodes.
We could store the nodes in vectors.
Note that the data could be
read in and placed in a structure:
stuct node{
int source, target;
}
(you can ignore cost for
your reachable problem)
A stack could be declared:
stack<node> s;
A vector to store nodes
could be declared:
vector<node> n;
A vector to store visited
nodes could be declared:
vector<node> v;
With these 3 STL structures,
you can solve the reachability problem.
Your assignment is to write
a program that reads in my graph (put the data in graph.txt) and prompts the
user for a source node. The program
should then print out a list of nodes reachable from the source node.
By the way, if you are going
to be a professonal C++ programmer, this should be the way that you approach
programming assignments. Research your
algorithm and implement it using the STL.
The STL is mature (debugged and optimized) and efficient code. It should be your choice for basic data
strutures.
This homework is due by
I have included a zip of a Microsoft
Visual C++ project that is a poor solution to the Dijkstra problem. If you run this project and specify graph.txt
as input, you can find if any 2 nodes are connected and also find the lowest
cost path between any 2 nodes. graph.zip